#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef char ElementType;

typedef struct TreeNode
{
    ElementType data;
    TreeNode *lChild;
    TreeNode *rChild;
} TreeNode, *Tree;

typedef struct QueueNode
{
    TreeNode *data;
    QueueNode *next;
} QueueNode, *Queue;

/*尾插法入队*/
bool EnQueue(Queue queue, TreeNode *tree_node)
{
    QueueNode *q_node = queue;
    while (q_node->next)
    {
        q_node = q_node->next;
    }
    QueueNode *node = (QueueNode *)malloc(sizeof(QueueNode));
    node->data = tree_node;
    node->next = q_node->next;
    q_node->next = node;
    return true;
}

/*出队*/
bool DeQueue(Queue queue, Tree &tree_node)
{
    if (!queue->next)
    {
        return false;
    }
    QueueNode *tmp_node = queue->next;
    tree_node = tmp_node->data;
    queue->next = tmp_node->next;
    free(tmp_node);
    return true;
}

bool EmptyQueue(Queue queue)
{
    return NULL == queue->next;
}

void BuildBTree(TreeNode *root, ElementType ch[])
{
    int len = strlen(ch);
    if (len == 0)
    {
        return;
    }
    else
    {
        root->data = ch[0];
        TreeNode *p_node = root;
        Queue queue = (Queue)malloc(sizeof(QueueNode));
        int index = 1;
        while (index < len)
        {
            TreeNode *t_node = new TreeNode();
            t_node->data = ch[index++];
            if (p_node->lChild && p_node->rChild)
            {
                DeQueue(queue, p_node);
            }
            if (!p_node->lChild)
            {
                p_node->lChild = t_node;
            }
            else if (!p_node->rChild)
            {
                p_node->rChild = t_node;
            }
            EnQueue(queue, t_node);
        }
    }
    // int len = strlen(ch);
    // Queue queue = (Queue)malloc(sizeof(QueueNode));
    // EnQueue(queue, root);
    // for (int i = 0; i < len; i++)
    // {
    //     TreeNode *tree_node;
    //     DeQueue(queue, tree_node);
    //     tree_node->data = ch[i];
    //     Tree left = new TreeNode();
    //     Tree right = new TreeNode();
    //     tree_node->lChild = left;
    //     tree_node->rChild = right;
    //     EnQueue(queue, left);
    //     EnQueue(queue, right);
    // }
}

void BFSTree(Tree tree)
{
    if (tree)
    {
        Queue queue = (Queue)malloc(sizeof(QueueNode));
        EnQueue(queue, tree);
        while (queue->next != NULL)
        {
            TreeNode *t_node;
            DeQueue(queue, t_node);
            printf("%2c", t_node->data);
            if (t_node->lChild)
            {
                EnQueue(queue, t_node->lChild);
            }
            if (t_node->rChild)
            {
                EnQueue(queue, t_node->rChild);
            }
        }
    }
}

void preOrderTree(Tree tree)
{
    if (tree)
    {
        printf("%2c", tree->data);
        preOrderTree(tree->lChild);
        preOrderTree(tree->rChild);
    }
}

void midOrderTree(Tree tree)
{
    if (tree)
    {
        midOrderTree(tree->lChild);
        printf("%2c", tree->data);
        midOrderTree(tree->rChild);
    }
}

void postOrderTree(Tree tree)
{
    if (tree)
    {
        postOrderTree(tree->lChild);
        postOrderTree(tree->rChild);
        printf("%2c", tree->data);
    }
}

int main()
{
    Tree tree = new TreeNode();
    char str[] = "abcdefghijk";
    BuildBTree(tree, str);
    printf("\n-------------preOrderTree--------------\n");
    preOrderTree(tree);
    printf("\n-------------midOrderTree--------------\n");
    midOrderTree(tree);
    printf("\n-------------postOrderTree--------------\n");
    postOrderTree(tree);
    printf("\n-------------BFSTree--------------\n");
    BFSTree(tree);
    return 0;
}